package cn.guyouda.algorithms;

import java.util.Hashtable;

import javax.management.RuntimeErrorException;

/**
 * 链表学习记录
 *
 * @author Youda
 */
public class MyLinkedList<T> {
    private Node next;
    private Node head;
    private Node tail;
    private int length;

    public MyLinkedList() {
        super();
    }


    public int getLength() {
        return length;
    }

    public void setLength(int length) {
        this.length = length;
    }

    /**
     * 添加节点
     *
     * @param data
     * @return
     */
    public Node addNode(T data) {

        Node newNode = new Node(data);
        newNode.data = data;
        if (head == null) {
            head = newNode;
            tail = head;
            setLength(1);
        } else {
            tail.next = newNode;
            tail = newNode;
            length = length++;
        }

        return head;
    }

    /**
     * 删除指定位置节点，index从零开始
     *
     * @param index
     * @return
     */
    public Boolean deleteNode(int index) {
        Boolean result = null;

        if (index < 1 || index >= getLength()) {
            return false;
        }

        if (index == 0) {
            head = head.next;
            length--;

            return true;
        }

        int i = 1;
        Node preNode = head;
        Node curNode = preNode.next;
        while (curNode != null) {
            if (i == index) {
                preNode.next = curNode.next;
                length--;
                return true;
            }
            preNode = curNode;
            curNode = curNode.next;
            i++;
        }

        return result;
    }

    /**
     * 删除重复节点
     * 使用额外存储空间，只需遍历一次
     */
    public void deleteDuplecate() {
        Hashtable<T, Integer> hashtable = new Hashtable<>();

        Node tmp = head;
        Node pre = null;

        while (tmp != null) {
            if (hashtable.containsKey(tmp.data)) {
                pre.next = tmp.next;
                length = length - 1;
            } else {
                hashtable.put(tmp.data, new Integer(1));
            }
            pre = tmp;
            tmp = tmp.next;
        }
    }

    /**
     * 查找倒数第index个节点
     * index从零开始
     * 利用两个引用分别指向相差index的节点，当第一个到达末尾时，第二个刚好到达指定位置
     *
     * @param index
     * @return
     */
    public Node findNode(int index) {

        if (index < 0 || index >= getLength()) {
            throw new RuntimeException("参数不符合要求");
        }
        Node p1 = head;
        Node p2 = head;

        for (int i = 0; i < index && p1 != null; i++) {
            p1 = p1.next;
        }
        if (p1 == null) {
            throw new RuntimeException("参数不符合要求");
        }

        while (p1.next != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p2;
    }

    /**
     * 链表反转
     */
    public void reverseList() {
        Node tempHead = head;
        Node curNode = head;
        Node preNode = null;

        while (curNode != null) {
            Node nextNode = curNode.next;
            if (nextNode == null) {
                tempHead = curNode;
            }
            curNode.next = preNode;
            preNode = curNode;
            curNode = nextNode;
        }
        this.head = tempHead;
    }

    /**
     * 获取中间节点
     * 利用两个指针同时往前移动，
     * p1每次移动两步，p2每次移动一步
     * 当p1到达尾部的时候p2刚好到达中间
     *
     * @return
     */
    public Node getMidNode() {
        Node p1 = head;
        Node p2 = head;

        while (p1 != null && p1.next != null && p1.next.next != null) {
            p1 = p1.next.next;
            p2 = p2.next;
        }

        return p2;
    }


    /**
     * 定义存储节点
     *
     * @author Youda
     */
    class Node {
        private Node next;
        private T data;

        public Node(T data) {
            this.data = data;
        }
    }


}
